// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include <queue>
#include "commoncppproblem117.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=117 lang=cpp
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
/*
    Node* connect(Node* root) 
    {
        if(root == NULL)
            return NULL;
        queue<Node*> q;
        Node *point;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i < size; i++)
            {
                point = q.front();
                q.pop();
                
                if(point->left)
                    q.push(point->left);
                if(point->right)
                    q.push(point->right);

                if(i == size -1)
                {
                    point->next = NULL;    
                }else
                {
                    point->next = q.front();
                }
            }
        }
        return root;
    }
*/
    Node* getNode(Node* node)
    {
        if(node == NULL)
            return NULL;
        if(node->left != NULL )
            return node->left;
        if(node->right != NULL )
            return node->right;
        if(node->next != NULL )
            return getNode(node->next);
        return NULL;
    }

    Node* connect(Node* root)
    {
        if(root == NULL)
            return root;
        if(root->left!=NULL && root->right!=NULL)
        {
            root->left->next = root->right;
        }
        if(root->left!=NULL && root->right == NULL)
        {
            root->left->next = getNode(root->next);
        }
        if(root->right!=NULL)
        {
            root->right->next = getNode(root->next);
        }


        //此处必须先连接右边节点，这样getNode()才会生效
        connect(root->right);
        connect(root->left);
        

        return root;

    }
     


};
// @lc code=end

